﻿#define _CRT_SECURE_NO_WARNINGS 1

//x 的平⽅根（easy）:https://leetcode.cn/problems/sqrtx/

//v1:
class Solution {
public:
    int mySqrt(int x) {
        for (long long i = 0; i <= x; i++)
        {
            if (i * i == x)    return i;
            else if (i * i > x)    return i - 1;
        }

        return -1;
    }
};

//v2:
class Solution {
public:
    int mySqrt(int x) {
        // if(x==1)
        // {
        //     return 1;
        // }
        //if(x<=1)   return x;
        long long  left = 0, right = x;
        while (left < right)
        {
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x)
            {
                left = mid;
            }
            else
            {
                right = mid - 1;
            }
        }

        return left;
    }
};


//⼭峰数组的峰顶（easy）:https://leetcode.cn/problems/peak-index-in-a-mountain-array/submissions/566483686/
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = arr.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (arr[mid] >= arr[mid + 1])    //降序
            {
                right = mid;
            }
            else                    //升序
            {
                left = mid + 1;
            }
        }

        return left;
    }
};